/*
Copyleft 2006 by T.S.Yo
*/

package exp.util;
import ec.*;
import ec.util.*;
import ec.select.*;

/* 
 * RankSelection.java
 * 
 * Created: 2006.11.24
 * By: T.S.Yo
 */

/**
 * Picks among the best <i>n</i> individuals in a population in 
 * direct proportion to their rankings sorted with fitness.
 * This is modified from Sean Luke's Best Selection, and is 
 * expensive to set up and bring down.
 *
 * @author T.S.Yo
 * @version 1.0 
 */
 
 
 
public class RankSelection extends SelectionMethod 
    {
    /** Default base */
    public static final String P_RANK = "rank";
    public static final String P_N = "n";
    public static final String P_PICKWORST = "pick-worst";
    /** CheckBoundary is 8 */
    public static final int CHECKBOUNDARY = 8;
    /** Sorted, normalized, totalized fitnesses for the population */
    public float[] sortedFit;
    /** Sorted population -- since I *have* to use an int-sized
        individual (short gives me only 16K), 
        I might as well just have pointers to the
        population itself.  :-( */
    public int[] sortedPop;

    /** Do we pick the worst instead of the best? */
    public boolean pickWorst;

    public int rankn;

    public Parameter defaultBase()
        {
        return SelectDefaults.base().push(P_RANK);
        }

    // don't need protoClone etc. 

    public void setup(final EvolutionState state, final Parameter base)
        {
        super.setup(state,base);
        
        Parameter def = defaultBase();
        
        rankn =
            state.parameters.getInt(base.push(P_N),def.push(P_N),1);
        if (rankn == 0 )
            state.output.fatal("n must be an integer greater than 0", base.push(P_N),def.push(P_N));
        
        pickWorst = state.parameters.getBoolean(base.push(P_PICKWORST),
                                                def.push(P_PICKWORST),false);
        }

    public void prepareToProduce(final EvolutionState s,
                                 final int subpopulation,
                                 final int thread)
        {
        // load sortedPop integers
        final Individual[] i = s.population.subpops[subpopulation].individuals;

        sortedPop = new int[i.length];
        for(int x=0;x<sortedPop.length;x++) sortedPop[x] = x;

        // sort sortedPop in increasing fitness order
        QuickSort.qsort(sortedPop, 
                        new SortComparatorL()
                            {
                            public boolean lt(long a, long b)
                                {
                                return ((Individual)(i[(int)b])).fitness.betterThan(
                                    ((Individual)(i[(int)a])).fitness);
                                }

                            public boolean gt(long a, long b)
                                {
                                return ((Individual)(i[(int)a])).fitness.betterThan(
                                    ((Individual)(i[(int)b])).fitness);
                                }
                            });

        // load sortedFit
        sortedFit = new float[Math.min(sortedPop.length,rankn)];
        int irank = sortedFit.length;
        float bestFit;
        if (pickWorst)
        {
            bestFit = ((Individual)(i[sortedPop[0]])).fitness.fitness();
            for(int x=0;x<sortedFit.length;x++)
            {
                if(((Individual)(i[sortedPop[x]])).fitness.fitness() > bestFit)
                    irank--;
                sortedFit[x] = (float)irank;
            }
        } else {
            bestFit = ((Individual)(i[sortedPop[sortedPop.length-1]])).fitness.fitness();
            for(int x=0;x<sortedFit.length;x++)
            {
                if(((Individual)(i[sortedPop[sortedPop.length-x-1]])).fitness.fitness() < bestFit)
                    irank--;
                sortedFit[x] = (float)irank;
            }
        }

        // organize the distributions.  All zeros in fitness is fine
        RandomChoice.organizeDistribution(sortedFit, true);
        }

    public int produce(final int subpopulation,
                       final EvolutionState state,
                       final int thread)
        {
        // Pick and return an individual from the population
        if (pickWorst)
            return sortedPop[RandomChoice.pickFromDistribution(
                                 sortedFit,state.random[thread].nextFloat(),CHECKBOUNDARY)];
        else
            return sortedPop[sortedPop.length - RandomChoice.pickFromDistribution(
                                 sortedFit,state.random[thread].nextFloat(),CHECKBOUNDARY) - 1];            
        }
    
    public void finishProducing(final EvolutionState s,
                                final int subpopulation,
                                final int thread)
        {
        // release the distributions so we can quickly 
        // garbage-collect them if necessary
        sortedFit = null;
        sortedPop = null;
        }    
    } 